Publications: (click title for abstract)

	Diogenes: Lightweight Scalable RSA Modulus Generation with a Dishonest Majority. (SBC 2020) M. Chen, C. Hazay, Y. Ishai, Y. Kashnikov, D. Micciancio, T. Riviere, a. shelat, M. Venkitasubramaniam, R. Wang. Blockchains and cryptocurrencies have resurrected demand for secure distributed key-generation protocols. We design and implement the first such protocol that remains practical even with thousands of parties, while offering security against an arbitrary number of corrupted parties. Our approach begins with the design of the ``best'' protocol for the task that is secure against passive corruption. We then obtain security against active corruption via efficient zero-knowledge proofs. In more detail, our passively secure protocol is based on a recent work of Chen et al. that extends the Boneh-Franklin protocol (J. ACM, 2001). Whereas the previous work relies on pairwise execution of an oblivious transfer protocol to implement secure multiplication, our protocol implements multiplication via a threshold additively homomorphic encryption (AHE) scheme based on the Ring LWE assumption. This results in significantly better throughput when the number of parties grows. In particular, it reduces the per-party communication from being linear in the number of parties to polylogarithmic. Then, we obtain our actively secure protocol by composing two zero-knowledge proof systems: (1) the Ligero sub-linear zero-knowledge proof system (Ames et al., CCS 2017), and (2) $\Sigma$-protocol for proving the knowledge of a discrete logarithm in unknown order groups (Shoup, Eurocrypt 2000). We implemented the passive variant of our protocol and ran experiments from 1,000 to 10,000 parties distributed geographically across multiple AWS cloud centers. For generating a 2048-bit modulus among 1,000 parties, our protocol executed in under 5 minutes in expectation. For 10,000 parties our protocol completed in 35 minutes in expectation. This is the first implementation of any MPC protocol that has been deployed at this scale.
	The Price of Active Security in Cryptographic Protocols. (EUROCRYPT 2020) C. Hazay, M. Venkitasubramaniam, M. Weiss. We construct the first actively-secure Multi-Party Computation (MPC) protocols with an arbitrary number of parties in the dishonest majority setting, for an arbitrary field F with constant communication overhead over the “passive-GMW” protocol (Goldreich, Micali and Wigderson, STOC ‘87). Our protocols rely on passive implementations of Oblivious Transfer (OT) in the boolean setting and Oblivious Linear function Evaluation (OLE) in the arithmetic setting. Previously, such protocols were only known over sufficiently large fields (Genkin et al. STOC ‘14) or a constant number of parties (Ishai et al. CRYPTO ‘08). Conceptually, our protocols are obtained via a new compiler from a passively-secure protocol for a distributed multiplication functionality Fmult , to an actively-secure protocol for general functionalities. Roughly, Fmult is parameterized by a linear-secret sharing scheme S, where it takes S-shares of two secrets and returns S-shares of their product. We show that our compilation is concretely efficient for sufficiently large fields, resulting in an over- head of 2 when securely computing natural circuits. Our compiler has two additional benefits: (1) it can rely on any passive implementation of Fmult, which, besides the standard implementation based on OT (for boolean) and OLE (for arithmetic) allows us to rely on implementations based on threshold cryptosystems (Cramer et al. Eurocrypt ‘01); and (2) it can rely on weaker-than-passive (i.e., imperfect/leaky) implementations, which in some parameter regimes yield actively-secure protocols with overhead less than 2. Instantiating this compiler with an “honest-majority” implementation of FMULT, we obtain the first honest-majority protocol with optimal corruption threshold for boolean circuits with constant communication overhead over the best passive protocol (Damgård and Nielsen, CRYPTO ‘07).	PDF
	Which Languages Have 4-Round Fully Black-Box Zero-Knowledge Arguments from One-Way Functions? (EUROCRYPT 2020) C. Hazay, R. Pass, M. Venkitasubramaniam. We prove that if a language $\cal L$ has a 4-round fully black-box zero-knowledge argument with negligible soundness based on one-way functions, then $\overline{\cal L} \in \mathsf{MA}$. Since $\mathsf{coNP} \subseteq \mathsf{MA}$ implies that the polynomial hierarchy collapses, our result implies that $\mathsf{NP}$-complete languages are unlikely to have 4-round fully black-box zero-knowledge arguments based on one-way functions. In TCC 2018, Hazay and Venkitasubramaniam, and Khurana, Ostrovsky, and Srinivasan demonstrated 4-round fully black-box zero-knowledge arguments for all languages in $\mathsf{NP}$ based on injective one-way functions. Their results also imply a 5-round protocol based on one-way functions. In essence, our result resolves the round complexity of fully black-box zero-knowledge arguments based on one-way functions.
	Going Beyond Dual Execution: MPC for Functions with Efficient Verification (PKC 2020) C. Hazay, a. shelat, M. Venkitasubramaniam. The dual execution paradigm of Mohassel and Franklin (PKC'06) and Huang, Katz and Evans (IEEE '12) shows how to achieve the notion of 1-bit leakage security at roughly twice the cost of semi-honest security for the special case of two-party secure computation. To date, there are no multi-party computation (MPC) protocols that offer such a strong trade-off between security and semi-honest performance. Our main result is to address this shortcoming by designing 1-bit leakage protocols for the multi-party setting, albeit for a special class of functions. We say that function $f(x,y)$ is efficiently verifiable by $g$ if the running time of $g$ is always smaller than $f$ and $g(x,y,z)=1$ if and only if $f(x,y)=z$. In the two-party setting, we first improve dual execution by observing that the "second execution" can be an evaluation of $g$ instead of $f$, and that by definition, the evaluation of $g$ is asymptotically more efficient. Our main MPC result is to construct a 1-bit leakage protocol for such functions from any passive protocol for $f$ that is secure up to additive errors and any active protocol for $g$. An important result by Genkin et al. (STOC '14) shows how the classic protocols by Goldreich et al. (STOC '87) and Ben-Or et al. (STOC '88) naturally support this property, which allows to instantiate our compiler with two-party and multi-party protocols. As another concrete example of instantiating our approach, we present a novel protocol for computing perfect matching that is secure in the 1-bit leakage model and whose communication complexity is less than the honest-but-curious implementations of textbook algorithms for perfect matching.
	A Round-Collapse Theorem for Computationally-Sound Protocols; or, TFNP is Hard (on Average) in Pessiland. R. Pass, M. Venkitasubramaniam. Consider the following two fundamental open problems in complexity theory: 1) Does a hard-on-average language in NP imply the existence of one-way functions? 2) Does a hard-on-average language in NP imply a hard problem in TFNP (i.e., the class of total NP search problem)? We show that the answer to (at least) one of these questions is yes. In other words, in Impagliazzo's Pessiland (where NP is hard-on-average, but one-way functions do not exist), TFNP is unconditionally hard (on average). This result follows from a more general theory of interactive average-case complexity, and in particular, a novel round-collapse theorem for computationally-sound protocols, analogous to Babai-Moran's celebrated round-collapse theorem for information-theoretically sound protocols. As another consequence of this treatment, we show that the existence of O(1)-round public-coin non-trivial arguments (i.e., argument systems that are not proofs) imply the existence of a hard-on-average problem in NP/poly.	PDF
	LevioSA: Lightweight Secure Arithmetic Computation. (CCS 2019) C. Hazay, Y. Ishai, A. Marcedone, M. Venkitasubramaniam. We study the problem of secure two-party computation of arithmetic circuits in the presence of active ("malicious") parties. This problem is motivated by privacy-preserving numerical computations, such as ones arising in the context of machine learning training and classification, as well as in threshold cryptographic schemes. In this work, we design, optimize, and implement anactively secure protocol for secure two-party arithmetic computation. A distinctive feature of our protocol is that it can make a fully modular black-box use of any passively secure implementation of oblivious linear function evaluation (OLE). OLE is a commonly used primitive for secure arithmetic computation, analogously to the role of oblivious transfer in secure computation for Boolean circuits. For typical (large but not-too-narrow) circuits, our protocol requires roughly 4 invocations of passively secure OLE per multiplication gate. This significantly improves over the recent TinyOLE protocol (Döttling et al., ACM CCS 2017), which requires 22 invocations of actively secure OLE in general, or 44 invocations of a specific code-based passively secure OLE. Our protocol follows the high level approach of the IPS compiler (Ishai et al., CRYPTO 2008, TCC 2009), optimizing it in several ways. In particular, we adapt optimization ideas that were used in the context of the practical zero-knowledge argument system Ligero (Ames et al., ACM CCS 2017) to the more general setting of secure computation, and explore the possibility of boosting efficiency by employing a "leaky" passively secure OLE protocol. The latter is motivated by recent (passively secure) lattice-based OLE implementations in which allowing such leakage enables better efficiency. We showcase the performance of our protocol by applying its implementation to several useful instances of secure arithmetic computation. On "wide" circuits, such as ones computing a fixed function on many different inputs, our protocol is 5x faster and transmits 4x less data than the state-of-the-art Overdrive (Keller et al., Eurocrypt 2018). Our benchmarks include a general passive-to-active OLE compiler, authenticated generation of "Beaver triples", and a system for securely outsourcing neural network classification. The latter is the first actively secure implementation of its kind, strengthening the passive security provided by recent related works (Mohassel and Zhang, IEEE S&P 2017; Juvekar et al., USENIX 2018).
	Round-Optimal Fully Black-Box Zero-Knowledge Arguments from One-Way Permutations. (TCC 2018) C. Hazay, M. Venkitasubramaniam. In this paper, we revisit the round complexity of designing zero-knowledge (ZK) arguments via a black-box construction from minimal assumptions. Our main result implements a 4-round ZK argument for any language in NP, based on injective one-way functions, that makes black-box use of the underlying function. As a corollary, we also obtain the first 4-round perfect zero-knowledge argument for NP based on claw-free permutations via a black-box construction and 4-round input-delayed commit-and-prove zero-knowledge argument based on injective one-way functions.	PDF
	Two-Round Adaptively Secure Multiparty Computation from Standard Assumptions. (TCC 2018) F. Benhamouda, H. Lin, A. Polychroniadou, M. Venkitasubramaniam. We present the first two-round multiparty computation (MPC) protocols secure against malicious adaptive corruption in the common reference string (CRS) model, based on DDH, LWE, or QR. Prior two-round adaptively secure protocols were known only in the two-party setting against semi-honest adversaries, or in the general multiparty setting assuming the existence of indistinguishability obfuscation (iO).Our protocols are constructed in two steps. First, we construct two-round oblivious transfer (OT) protocols secure against malicious adaptive corruption in the CRS model based on DDH, LWE, or QR. We achieve this by generically transforming any two-round OT that is only secure against static corruption but has certain oblivious sampleability properties, into a two-round adaptively secure OT. Prior constructions were only secure against semi-honest adversaries or based on iO.Second, building upon recent constructions of two-round MPC from two-round OT in the weaker static corruption setting [Garg and Srinivasan, Benhamouda and Lin, Eurocrypt’18] and using equivocal garbled circuits from [Canetti, Poburinnaya and Venkitasubramaniam, STOC’17], we show how to construct two-round adaptively secure MPC from two-round adaptively secure OT and constant-round adaptively secure MPC, with respect to both malicious and semi-honest adversaries. As a corollary, we also obtain the first 2-round MPC secure against semi-honest adaptive corruption in the plain model based on augmented non-committing encryption (NCE), which can be based on a variety of assumptions, CDH, RSA, DDH, LWE, or factoring Blum integers. Finally, we mention that our OT and MPC protocols in the CRS model are, in fact, adaptively secure in the Universal Composability framework.
	Round-Optimal Secure Multi-Party Computation. (CRYPTO 2018) S. Halevi, C. Hazay, A. Polychroniadou, M. Venkitasubramaniam. Secure multi-party computation (MPC) is a central cryptographic task that allows a set of mutually distrustful parties to jointly compute some function of their private inputs where security should hold in the presence of a malicious adversary that can corrupt any number of parties. Despite extensive research, the precise round complexity of this ``standard-bearer'' cryptographic primitive is unknown. Recently, Garg, Mukherjee, Pandey and Polychroniadou, in Eurocrypt 2016 demonstrated that the round complexity of any MPC protocol relying on black-box proofs of security in the plain model must be at least four. Following this work, independently Ananth, Choudhuri and Jain, CRYPTO 2017 and Brakerski, Halevi, and Polychroniadou, TCC 2017 made progress towards solving this question and constructed four-round protocols based on non-polynomial time assumptions. More recently, Ciampi, Ostrovsky, Siniscalchi and Visconti in TCC 2017 closed the gap for two-party protocols by constructing a 4-round protocol from polynomial-time assumptions. In another work, Ciampi, Ostrovsky, Siniscalchi and Visconti TCC 2017 showed how to design a 4-round multi-party protocol for the specific case of multi-party coin-tossing. In this work, we resolve this question by designing a 4-round actively secure multi-party (two or more parties) protocol for general functionalities under standard polynomial-time hardness assumptions.	PDF
	A Unified Approach to Constructing Black-box UC Protocols in Trusted Setup Models. (TCC 2017) S. Kiyoshima, H. Lin, M. Venkitasubramaniam. We present a unified framework for obtaining black-box constructions of Universal Composable (UC) protocol in trusted setup models. Our result is analogous to the unified framework of Lin, Pass, and Venkitasubramaniam [STOC'09, Asiacrypt'12] that, however, only yields non-black-box constructions of UC protocols. Our unified framework shows that to obtain black-box constructions of UC protocols, it suffices to implement a special purpose commitment scheme that is, in particular, concurrently extractable using a given trusted setup. Using our framework, we improve black-box constructions in the common reference string and tamper-proof hardware token models by weakening the underlying computational and setup assumptions.	PDF
	Actively Secure Garbled Circuits with Constant Communication Overhead in the Plain Model. (TCC 2017) C. Hazay, Y. Ishai, M. Venkitasubramaniam. We consider the problem of constant-round secure two-party computation in the presence of active (malicious) adversaries. We present the first protocol that has only a constant multiplicative communication overhead compared to Yao's protocol for passive adversaries and can be implemented in the plain model by only making a black-box use of (parallel) oblivious transfer and a pseudo-random generator. This improves over the polylogarithmic overhead of the previous best protocol. A similar result could previously be obtained only in an amortized setting, using preprocessing, or by assuming bit-oblivious-transfer as an ideal primitive that has a constant cost. We present two variants of this result, one which is aimed at minimizing the number of oblivious transfers and another which is aimed at optimizing concrete efficiency. Our protocols are based on a novel combination of previous techniques together with a new efficient protocol to certify that pairs of strings transmitted via oblivious transfer satisfy a global relation. The communication complexity of the second variant of our protocol can beat the best previous protocols even for realistic values of the circuit size and the security parameter. This variant is particularly attractive in the offline-online setting, where the online cost is dominated by a single evaluation of an authenticated garbled circuit, and can also be made non-interactive using the Fiat-Shamir heuristic.	PDF
	Ligero: Lightweight Sublinear Arguments without a Trusted Setup. (CCS 2017) S. Ames, C. Hazay, Y. Ishai, M. Venkitasubramaniam. We design and implement a simple zero-knowledge argument protocol for NP whose communication complexity is proportional to the square-root of the verification circuit size. The protocol can be based on any collision-resistant hash function. Alternatively, it can be made non-interactive in the random oracle model, yielding concretely efficient zk-SNARKs that do not require a trusted setup or public-key cryptography. Our protocol is attractive not only for very large verification circuits but also for moderately large circuits that arise in applications. For instance, for verifying a SHA-256 preimage in zero-knowledge with $2^{-40}$ soundness error, the communication complexity is roughly 44KB (or less than 34KB under a plausible conjecture), the prover running time is 140 ms, and the verifier running time is 62 ms. This proof is roughly 4 times shorter than a similar proof of ZKB++ (Chase et al., CCS 2017), an optimized variant of ZKBoo (Giacomelli et al., USENIX 2016). The communication complexity of our protocol is independent of the circuit structure and depends only on the number of gates. For $2^{-40}$ soundness error, the communication becomes smaller than the circuit size for circuits containing roughly 3 million gates or more. Our efficiency advantages become even bigger in an amortized setting, where several instances need to be proven simultaneously. Our zero-knowledge protocol is obtained by applying an optimized version of the general transformation of Ishai et al. (STOC 2007) to a variant of the protocol for secure multiparty computation of Damg{\aa}rd and Ishai (Crypto 2006). It can be viewed as a simple zero-knowledge interactive PCP based on ``interleaved'' Reed-Solomon codes.
	Equivocating Yao: Constant-Rounds Adaptively Secure Multiparty Computation in the Plain Model. (STOC 2017) R. Canetti, O. Poburinnaya, M. Venkitasubramaniam. Invited to SIAM Journal of Computing, special issue for selected papers of STOC 2017. Yao's garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds? We answer this question in the affirmative. We define a new type of encryption, called functionally equivocal encryption (FEE),and show that when Yao's scheme is implemented with an FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one way function. Combining our scheme with non-committing encryption, we obtain the first two-message, two-party computation protocol, and the first constant-round multiparty computation protocol, in the plain model, that are secure against semi-honest adversaries who can adaptively corrupt all parties. A number of extensions and applications are described within.	PDF
	Better Two-Round Adaptive Multi-Party Computation. (PKC 2017) R. Canetti, O. Poburinnaya, M. Venkitasubramaniam. The only known two-round multi-party computation protocol that withstands adaptive corruption of all parties is the ingenious protocol of Garg and Polychroniadou [GP] (TCC 15). We present protocols that improve on the GP protocol in a number of ways. First, concentrating on the semi-honest case and taking a different approach than GP, we show a two-round, adaptively secure protocol where: Only a global (i.e., non-programmable) reference string is needed. In contrast, in GP the reference string is programmable, even in the semi-honest case. Only polynomially-secure indistinguishability obfuscation for circuits and injective one way functions are assumed. In GP, sub-exponentially secure IO is assumed. Second, in the malicious setting, we show how to make the GP protocol have only RAM complexity. For this we construct the first statistically-sound non-interactive Zero-Knowledge scheme with RAM complexity.	PDF
	Scalable Multi-Party Private Set-Intersection (PKC 2017) C. Hazay, M. Venkitasubramaniam. In this work we study the problem of private set-intersection in the multi-party setting and design two protocols with the following improvement compared to prior work. First, our protocols take a new approach of leveraging the 2PC protocol of Freedman, Nissim and Pinkas (Eurocrypt 2004) and minimize the usage of a broadcast channel, where our semi-honest protocol does not make any use of such a channel. In addition, the communication complexity of our protocols scale with the number of parties. More concretely, (1) our first semi-honest secure protocol with communication complexity that is linear in the input sizes, namely $O(\sum_{i=1}^n m_i)$ where $m_i$ is the size of $P_i$'s input set, whereas the computational overhead is quadratic in the input sizes only for a designated party, and linear for the rest. (2) Our second protocol is proven secure in the malicious setting. This protocol induces communication complexity $O(\sum_{i=1}^2 m_i + n^2)$ where $n$ is the number of parties.	PDF
	Constant-Round Adaptively Secure Protocols in the Tamper-Proof Hardware Model (PKC 2017) C. Hazay, A. Polychroniadou, M. Venkitasubramaniam. Achieving constant-round adaptively secure protocols (where all parties can be corrupted) in the plain model is a notoriously hard problem. Very recently, three works published in TCC 2015 (Dachman-Soled et al., Garg and Polychroniadou, Canetti et al.), solved the problem in the Common Reference String (CRS) model. In this work, we present a constant-round adaptive UC-secure computation protocol for all well-formed functionalities in the tamper-proof hardware model using stateless tokens from only one-way functions. In contrast, all prior works in the CRS model require very strong assumptions, in particular, the existence of indistinguishability obfuscation. As a corollary to our techniques, we present the first adaptively secure protocols in the Random Oracle Model (ROM) with round complexity proportional to the depth of circuit implementing the functionality. Our protocols are secure in the Global Random Oracle Model introduced recently by Canetti, Jain and Scafuro in CCS 2014 that provides strong compositional guarantees. More precisely, we obtain an adaptively secure UC-commitment scheme in the global ROM assuming only one-way functions. In comparison, the protocol of Canetti, Jain and Scafuro achieves only static security and relies on the specific assumption of Discrete Diffie-Hellman assumption (DDH).	PDF
	Composable Adaptive Secure Protocols without Setup under Polytime Assumptions. (TCC 2016-B) C. Hazay, M. Venkitasubramaniam. All previous constructions of general multiparty computation protocols that are secure against adaptive corruptions in the concurrent setting either require some form of setup or non-standard assumptions. In this paper we provide the first general construction of secure multi-party computation protocol without any setup that guarantees composable security in the presence of an adaptive adversary based on standard polynomial-time assumptions. We prove security under the notion of "UC with super-polynomial helpers" introduced by Canetti et al. (FOCS 2010), which is closed under universal composition and implies "super-polynomial-time simulation". Moreover, our construction relies on the underlying cryptographic primitives in a black-box manner. Next, we revisit the zero-one law for two-party secure functions evaluation initiated by the work of Maji, Prabhakaran and Rosulek (CRYPTO 2010). According to this law, every two-party functionality is either trivial (meaning, such functionalities can be reduced to any other functionality) or complete (meaning, any other functionality can be reduced to these functionalities) in the Universal Composability (UC) framework. As our second contribution, assuming the existence of a simulatable public-key encryption scheme, we establish a zero-one law in the adaptive setting. Our result implies that every two-party non-reactive functionality is either trivial or complete in the UC framework in the presence of adaptive, malicious adversaries.	PDF
	Composable Security in the Tamper Proof Hardware Model under Minimal Complexity. (TCC 2016-B) C. Hazay, A. Polychroniadou, M. Venkitasubramaniam. We put forth a new formulation of tamper-proof hardware in the Global Universal Composable (GUC) framework introduced by Canetti et al. in TCC 2007. Almost all of the previous works rely on the formulation by Katz in Eurocrypt 2007 and this formulation does not fully capture tokens in a concurrent setting. We address these shortcomings by relying on the GUC framework where we make the following contributions: We construct secure Two-Party Computation (2PC) protocols for general functionalities with optimal round complexity and computational assumptions using stateless tokens. More precisely, we show how to realize arbitrary functionalities with GUC security in two rounds under the minimal assumption of One-Way Functions (OWFs). Moreover, our construction relies on the underlying function in a black-box way. As a corollary, we obtain feasibility of Multi-Party Computation (MPC) with GUC-security under the minimal assumption of OWFs. As an independent contribution, we identify an issue with a claim in a previous work by Goyal, Ishai, Sahai, Venkatesan and Wadia in TCC 2010 regarding the feasibility of UC-secure computation with stateless tokens assuming collision-resistant hash-functions (and the extension based only on one-way functions). We then construct a 3-round MPC protocol to securely realize arbitrary functionalities with GUC-security starting from any semi-honest secure MPC protocol. For this construction, we require the so-called one-many commit-and-prove primitive introduced in the original work of Canetti, Lindell, Ostrovsky and Sahai in STOC 2002 that is round-efficient and black-box in the underlying commitment. Using specially designed ``input-delayed'' protocols we realize this primitive (with a 3-round protocol in our framework) using stateless tokens and one-way functions (where the underlying one-way function is used in a black-box way).	PDF
	On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography (INDOCRYPT 2016) D. Miller, A. Scrivener, J. Stern, M. Venkitasubramaniam. Goldreich and Izsak (Theory of Computing, 2012) initiated the research on understanding the role of negations in circuits implementing cryptographic primitives, notably, considering one-way functions and pseudo-random generators. More recently, Guo, Malkin, Oliveira and Rosen (TCC, 2015) determined tight bounds on the minimum number of negations gates (i.e., negation complexity) of a wide variety of cryptographic primitives including pseudo-random functions, error-correcting codes, hardcore-predicates and randomness extractors. We continue this line of work to establish the following results: First, we determine tight lower bounds on the negation complexity of collision-resistant and target collision-resistant hash-function families. Next, we examine the role of injectivity and surjectivity on the negation complexity of one-way functions. Here we show that, Assuming the existence of one-way injections, there exists a monotone one-way injection. Furthermore, we complement our result by showing that, even in the worst-case, there cannot exist a monotone one-way injection with constant stretch. Assuming the existence of one-way permutations, there exists a monotone one-way surjection. Finally, we show that there exists list-decodable codes with monotone decoders. In addition, we observe some interesting corollaries to our results.	PDF
	On the Power of Two-Party Computation. (CRYPTO 2016) C. Hazay, M. Venkitasubramaniam. Ishai, Kushilevitz, Ostrovsky and Sahai (STOC 2007, SIAM JoC 2009) introduced the powerful "MPC-in-the-head" technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a "black-box" way. In this work, we extend this technique and provide a generic transformation of any semi-honest secure two-party computation (2PC) protocol (with mild adaptive security guarantees) in the so called oblivious-transfer hybrid model to an adaptive ZK proof for any $\mathsf{NP}$-language, in a ``black-box'' way assuming only one-way functions. Our basic construction based on Goldreich-Micali-Wigderson's 2PC protocol yields an adaptive ZK proof with communication complexity proportional to quadratic in the size of the circuit implementing the $\mathsf{NP}$ relation. Previously such proofs relied on an expensive Karp reduction of the $\mathsf{NP}$ language to Graph Hamiltonicity (Lindell and Zarosim (TCC 2009, Journal of Cryptology 2011)). We also improve our basic construction to obtain the first linear-rate adaptive ZK proofs by relying on efficient maliciously secure 2PC protocols. Core to this construction is a new way of transforming 2PC protocols to efficient (adaptively secure) instance-dependent commitment schemes. As our second contribution, we provide a general transformation to construct a randomized encoding of a function $f$ from any 2PC protocol that securely computes a related functionality (in a black-box way). We show that if the 2PC protocol has mild adaptive security guarantees then the resulting randomized encoding (RE) can be decomposed to an offline/online encoding. As an application of our techniques, we show how to obtain a ZK proof for any $\mathsf{NP}$ language that is black-box in the underlying one-way function with an "input-delayed" property and without relying on expensive Karp reductions. Namely, the honest prover's algorithm does not require the actual statement to be proved until the last round. We further generalize this to obtain a "commit and prove" protocol with the same property where the prover commits to a witness $w$ in the second message and proves a statement $x$ regarding the witness $w$ in zero-knowledge where the statement is determined only in the last round. This improves previous constructions of Lapidot and Shamir (Crypto 1990) was designed specifically for the Graph Hamiltonicity problem and relied on the underlying primitives in a non-black-box way.	PDF
	Privacy Enhancement for Interconnected Vehicles via Secure Multiparty Computation. (ITS World Congress 2016) S. Markandeya, M. Venkitasubramaniam. Vehicle-to-vehicle communication is wireless transmission of data between vehicles where the goal is to prevent accidents by sharing speed and position data. As has been well established, V2V has the potential to dramatically improve highway safety, however, the same technology raises serious concerns regarding security and privacy of the data being created, collected and shared. In this work, we identify a particular privacy vulnerability of the proposed Security Credential Management System (SCMS) and suggest an alternative mechanism to provide stronger privacy guarantees by using a powerful tool from modern cryptography known as secure multiparty computation.
	What Security Can We Achieve in 4-rounds. (SCN 2016) C. Hazay, M. Venkitasubramaniam. Katz and Ostrovsky (Crypto 2004) proved that five rounds are necessary for stand-alone general black-box constructions of secure two-party protocols and at least four rounds are necessary if only one party needs to receive the output. Recently, Ostrovsky, Richelson and Scafuro (Crypto 2015) proved optimality of this result by showing how to realize arbitrary functionalities in four rounds where only one party receives the output via a black-box construction (and an extension to five rounds where both parties receive the output). In this paper we study the question of what security is achievable for stand-alone two-party protocols within four rounds. We first provide a four-round two-party protocol for coin-tossing that achieves $1/p$-simulation security (i.e. simulation fails with probability at most $1/p+\ngl$), in the presence of malicious corruptions. Next, we provide a four-round two-party protocol for general functionalities, where both parties receive the output, that achieves $1/p$-security in the presence of malicious adversaries corrupting one of the parties, and full security in the presence of non-aborting malicious adversaries corrupting the other party. Next, we provide a three-round oblivious-transfer protocol, that achieves $1/p$--simulation security against arbitrary malicious senders, while simultaneously guaranteeing a meaningful notion of privacy against malicious corruptions of either party. Finally, we show that the simulation-based security guarantees for our three-round protocols are optimal by proving that 1/p-simulation security is impossible to achieve against both parties in three rounds or less when requiring some minimal guarantees on the privacy of their inputs.	PDF
	Secure Computation from Millionaires. (ASIACRYPT 2015) a. shelat, M. Venkitasubramaniam The standard method for designing a secure computation protocol for function f first transforms f into either a circuit or a RAM program and then applies a generic secure computation protocol that either handles boolean gates or translates the RAM program into oblivious RAM instructions. In this paper, we show a large class of functions for which a different iterative approach to secure computation results in more efficient protocols. The first such examples of this technique was presented by Aggrawal, Mishra, and Pinkas (J. of Cryptology, 2010) for computing the median; later, Brickell and Shmatikov (Asiacrypt 2005) showed a similar technique for shortest path problems. We generalize the technique in both of those works and show that it applies to a large class of problems including certain matroid optimizations, sub-modular optimization, convex hulls, and other scheduling problems. The crux of our technique is to securely reduce these problems to secure comparison operations and to employ the idea of gradually releasing part of the output. We then identify conditions under which both of these techniques for protocol design are compatible with achieving simulation-based security in the honest-but-curious and covert adversary models. In special cases such as median, we also show how to achieve malicious security.	PDF
	On the Black-Box Complexity of UC-Commitments. (ASIACRYPT 2015) C. Hazay, M. Venkitasubramaniam. In this work, we study the intrinsic complexity of black-box Universally Composable (UC) secure computation based on general assumptions. We present a thorough study in various corruption modelings while focusing on achieving security in the common reference string (CRS) model. Our results involve the following: Static UC secure computation. Designing the first static UC secure oblivious transfer protocol based on public-key encryption and stand-alone semi-honest oblivious transfer. As a corollary we obtain the first black-box constructions of UC secure computation assuming only two-round semi-honest oblivious transfer. One-sided UC secure computation. Designing adaptive UC secure two-party computation with single corruptions assuming public-key encryption with oblivious ciphertext generation. Adaptive UC secure computation. Designing adaptively secure UC commitment scheme assuming only public-key encryption with oblivious ciphertext generation. As a corollary we obtain the first black-box constructions of adaptive UC secure computation assuming only (trapdoor) simulatable public-key encryption (as well as a variety of concrete assumptions). We remark that such a result was not known even under non-black-box constructions.	PDF
	Resettably Sound Zero-Knoweldge Arguments from OWFs - the (semi) Black-Box way. (TCC 2015) R. Ostrovsy, A. Scafuro, M. Venkitasubramaniam. We construct a constant-round resettably-sound zero-knowledge argument of knowledge based on black-box use of any one-way function. Resettable-soundness was introduced by Barak, Goldreich, Goldwasser and Lindell (FOCS 01) and is a strengthening of the soundness requirement in interactive proofs demanding that soundness should hold even if the malicious prover is allowed to “reset” and “restart” the verifier. In their work they show that resettably-sound ZK arguments require non-black-box simulation techniques, and also provide the first construction based on the breakthrough simulation technique of Barak (FOCS 01). All known implementations of Barak’s non-black-box technique required non-black-box use of a collision-resistance hash-function (CRHF). Very recently, Goyal, Ostrovsky, Scafuro and Visconti (STOC 14) showed an implementation of Barak’s technique that needs only black-box access to a collision-resistant hash-function while still having a non-black-box simulator. (Such a construction is referred to as semi black-box.) Plugging this implementation in the BGGL’s construction yields the first resettably-sound ZK arguments based on black-box use of CRHFs. However, from the work of Chung, Pass and Seth (STOC 13) and Bitansky and Paneth (STOC13), we know that resettably-sound ZK arguments can be constructed from non-black-box use of any one-way function (OWF), which is the minimal assumption for ZK arguments. Hence, a natural question is whether it is possible to construct resettably-sound zero-knowledge arguments from black-box use of any OWF only. In this work we provide a positive answer to this question thus closing the gap between black-box and non-black-box constructions for resettably-sound ZK arguments.	PDF
	Concurrent Zero Knowledge, Revisited (Journal of Cryptology, 2014) R. Pass, W. Tseng, M. Venkitasubramaniam. We show a parallel-repetition theorem for constant-round Arthur-Merlin Proofs, using an efficient reduction. As a consequence, we show that parallel repetition reduces the soundness-error at an optimal rate (up to a negligible factor) in constant-round public-coin argument systems, and constant-round public-coin proofs of knowledge. The former of these results resolves an open question posed by Bellare, Impagliazzo and Naor (FOCS '97).	PDF
	Cloud-based Secure Health Monitoring: Optimizing Fully-Homomorphic Encryption for Streaming Algorithms (CCSNA 2014) A. Page, O. Kocabas, S. Ames, M. Venkitasubramaniam, T. Soyata. There are many incentives for healthcare providers to shift their datacenters to the cloud. However, privacy of patient health information is a major concern when processing medical data off-site. One possible solution is the use of Fully Homomorphic Encryption (FHE), but this solution is too slow for most applications. We present a technique that increases efficiency and parallelism for certain algorithms under FHE. Through experiments and simulations, we demonstrate that our method yields about 20x speedup in a sample application. This is a significant step towards practical FHE-based medical remote monitoring
	4-Round Resettably- Sound Zero Knowledge (TCC 2014) K. Chung, R. Ostrovsky, R. Pass, M. Venkitasubramaniam, I. Visconti. While 4-round constructions of zero-knowledge arguments are known based on the existence of one-way functions, constuctions of resettably-sound zero-knowledge arguments require either stronger assumptions (the existence of a fully-homomorphic encryption scheme), or more communication rounds. We close this gap by demonstrating a 4- round resettably-sound zero-knowledge argument for $\mathsf{NP}$ based on the existence of one-way functions.	PDF
	On Adaptively Secure Protocols (SCN 2014) M. Venkitasubramaniam Adaptive security captures the capability of an adversary to adaptively affect a system during the course of its computation based on partial information gathered. In this work, we explore the theoretical complexity of achieving adaptive security in two settings: Adaptive UC-Secure Computation: We provide a round-efficient compiler that transforms any stand-alone semi-honest adaptively secure multiparty computation to adaptive UC-security. Recently, Dana et. al (Asiacrypt 2013) showed how to acheive adaptive UCsecurity in any trusted setup under minimal assumptions. They achieve this by constructing an O(n)-round adaptively secure concurrent non-malleable commitment scheme. The main contribution of our work shows how to achieve the same in O(1)-rounds. Zero-Knowledge with Adaptive Inputs: Lin and Pass in (TCC 2011) gave first constructions of concurrent non-malleable zero-knowledge proofs secure w.r.t. adaptively chosen inputs in the plain model in a restricted setting, namely, where the adversary can only ask for proofs of true (adaptively-chosen) statements. We extend their definition to the fully-adaptive setting and show how to construct a protocol that satisfies this definition. As an independent contribution we provide a simple and direct compilation of any semi-honest secure protocol to a fully concurrently secure protocol under polynomialtime assumptions in the Angel-Based UC-Security.	PDF
	Adaptive and Concurrent Secure Computation from New Adaptive, Non-Malleable Commitments (Asiacrypt 2013) D. Dachman-Soled, T. Malkin, M. Raykova, M. Venkitasubramaniam. We present a unified approach for obtaining general secure computation that achieves adaptive-Universally Composable (UC)-security. Using our approach we essentially obtain all previous results on adaptive concurrent secure computation, both in relaxed models (e.g., quasi-polynomial time simulation), as well as trusted setup models (e.g., the CRS model, the imperfect CRS model). This provides conceptual simplicity and insight into what is required for adaptive and concurrent security, as well as yielding improvements to set-up assumptions and/or computational assumptions in known models. Additionally, we provide the first constructions of concurrent secure computation protocols that are adaptively secure in the timing model, and the non-uniform simulation model. As a corollary we also obtain the first adaptively secure multiparty computation protocol in the plain model that is secure under bounded-concurrency. Conceptually, our approach can be viewed as an adaptive analogue to the recent work of Lin, Pass and Venkitasubramaniam [STOC '09], who considered only non-adaptive adversaries. Their main insight was that the non-malleability requirement could be decoupled from the simulation requirement to achieve UCsecurity. A main conceptual contribution of this work is, quite surprisingly, that it is still the case even when considering adaptive security. A key element in our construction is a commitment scheme that satisfies a strong definition of non-malleability. Our new primitive of concurrent equivocal nonmalleable commitments, intuitively, guarantees that even when a man-in-the-middle adversary observes concurrent equivocal commitments and decommitments, the binding property of the commitments continues to hold for commitments made by the adversary. This definition is stronger than previous ones, and may be of independent interest. Previous constructions that satisfy our definition have been constructed in setup models, but either require existence of stronger encryption schemes such as CCA-secure encryption or require independent “trapdoors” provided by the setup for every pair of parties to ensure non-malleability. A main technical contribution of this work is to provide a construction that eliminates these requirements and requires only a single trapdoor.	PDF
	The Generalized Randomized Iterate and Its Application to New Efficient Constructions of UOWHFs from Regular One-Way Functions (Asiacrypt 2012) S. Ames, R. Gennaro, M. Venkitasubramaniam. This paper presents the Generalized Randomized Iterate of a (regular) one-way function f and showthat it can be used to build Universal One-Way Hash Function (UOWHF) families with O(n2) key length. We then show that Shoup's technique for UOWHF domain extension can be used to improve the efficiency of the previous construction. We present the Reusable Generalized Randomized Iterate which consists of k ≥ n + 1 iterations of a regular one-way function composed at each iteration with a pairwise independent hash function, where we only use log k such hash functions, and we "schedule" them according to the same scheduling of Shoup's domain extension technique. The end result is a UOWHF construction from regular one-way functions with an O(n log n) key. These are the first such efficient constructions of UOWHF from regular one-way functions of unknown regularity. Finally we show that the Shoup's domain extension technique can also be used in lieu of derandomization techniques to improve the efficiency of PRGs and of hardness amplification constructions for regular one-way functions.	PDF
	A Unified Framework for UC from Only OT (Asiacrypt 2012) H. Lin, R. Pass, M. Venkitasubramaniam. In [LPV09], the authors presented a unified framework for constructing Universally Composable (UC) secure computation protocols, assuming only enhanced trapdoor permutations. In this work, we weaken the hardness assumption underlying the unified framework to only the existence of a stand-alone secure semi-honest Oblivious Transfer (OT) protocol. The new framwork directly implies new and improved UC feasibility results from only the existence of a semi-honest OT protocol in various models. Since in many models, the existence of UC-OT implies the existence of a semi-honest OT protocol. Furthermore, we show that by relying on a more fine-grained analysis of the unified framework, we obtain concurrently secure computation protocols with super-polynomial-time simulation (SPS), based on the necessary assumption of the existence of a semi-honest OT protocol that can be simulated in super-polynomial times. When the underlying OT protocol has constant rounds, the SPS secure protocols constructed also have constant rounds. This yields the first construction of constant-round secure computation protocols that satisfy a meaningful notions of concurrent security (i.e., SPS security) based on tight assumptions. A notable corollary following from our new unifed framwork is that stand-alone (or bounded-concurrent) password authenticated key-exchange protocols (PAKE) can be constructed from only semi-honest OT protocols; combined with the result of [Nguyen05] that the existence of PAKE protocols implies that of OT, we derive a tight characterization of PAKE protocols.	PDF
	Towards Non-Black-Box Lower Bounds in Cryptography (TCC 2011) R. Pass, Wei-Lung D. Tseng, M. Venkitasubramaniam. We consider average-case strengthenings of the traditional assumption that coNP is not contained in AM. Under these assumptions, we rule out generic and potentially non-black-box constructions of various cryptographic primitives (e.g., one-way permutations, collision-resistant hash-functions, constant-round statistically hiding commitments, and constant-round black-box zero-knowledge proofs for NP) from one-way functions, assuming the security reductions are black-box.	PDF
	Concurrent Non-Malleable Zero Knowledge Proofs (CRYPTO 2010) H. Lin, R. Pass, Wei-Lung D. Tseng, M. Venkitasubramaniam. Concurrent non-malleable zero-knowledge (NMZK) considers the concurrent execution of zero-knowledge protocols in a setting where the attacker can simultaneously corrupt multiple provers and verifiers. Barak, Prabhakaran and Sahai (FOCS’06) recently provided the first construction of a concurrent NMZK protocol without any set-up assumptions. Their protocol, however, is only computationally sound (a.k.a., a concurrent NMZK argument). In this work we present the first construction of a concurrent NMZK proof without any set-up assumptions. Our protocol requires poly(n) rounds assuming one-way functions, or Õ(log n) rounds assuming collision-resistant hash functions. As an additional contribution, we improve the round complexity of concurrent NMZK arguments based on one-way functions (from poly(n) to Õ(log n)), and achieve a near linear (instead of cubic) security reductions. Taken together, our results close the gap between concurrent ZK protocols and concurrent NMZK protocols (in terms of feasibility, round complexity, hardness assumptions, and tightness of the security reduction).	PDF
	Eye for an Eye: On Concurrent Zero-Knowledge in the Timing Model. (TCC 2010) R. Pass, Wei-Lung D. Tseng, M. Venkitasubramaniam. We present new and efficient concurrent zero-knowledge protocols in the timing model. In contrast to earlier work-which through artificially-imposed delays require every protocol execution to run at the speed of the slowest link in the network-our protocols essentially only delay messages based on the actual response time of each verifier (which can be significantly smaller).	PDF
	Private Coins versus Public Coins in Zero-Knowledge Proof Systems. (TCC 2010) R. Pass, M. Venkitasubramaniam. Goldreich-Krawczyk (Siam J of Comp'96) showed that only languages in BPP have constant-round public-coin black-box zero-knowledge protocols. We extend their lower bound to fully black-box" private- coin protocols based on one-way functions. More precisely, we show that only languages in BPPSam-where Sam is a "collision-finding" oracle in analogy with Simon (Eurocrypt'98) and Haitner et. al (FOCS'07)-can have constant-round fully black-box zero-knowledge proofs; the same holds for constant-round fully black-box zero-knowledge arguments with sublinear verifier communication complexity. We also establish nearlinear lower bounds on the round complexity of fully black-box concurrent zero-knowledge proofs (or arguments with sublinear verifier communication) for languages outside BPPSam. The technique used to establish these results is a transformation from private-coin protocols into Sam-relativized public-coin protocols; for the case of fully black-box protocols based on one-way functions, this transformation preserves zero knowledge, round complexity and communication complexity.	PDF
	A Unified Framework for Concurrent Security: Universal Composability from Stand-alone Non-malleability. (STOC 2009) H. Lin, R. Pass and M. Venkitasubramaniam. We present a unified framework for obtaining Universally Composable (UC) protocols by relying on stand-alone secure non-malleable commitments Essentially all results on concurrent secure computation-both in relaxed models (e.g., quasi-polynomial time simulation), or with trusted set-up assumptions (e.g., the CRS model, the imperfect CRS model, or the timing model)-are obtained as special cases of our framework. This not only leads to conceptually simpler solutions, but also to improved set-up assumptions, round-complexity, and computational assumptions. Additionally, this framework allows us to consider new relaxed models of security: we show that UC security where the adversary is a uniform PPT but the simulator is allowed to be a non-uniform PPT (i.e., essentially, traditional UC security, but with a non-uniform reduction) is possible without any trusted set-up. This gives the first results on concurrent secure computation without set-up, which can be used for securely computing ``computationally-sensitive'' functionalities (e.g., data-base queries, ``proof of work''-protocols, or playing bridge on the Internet).	PDF
	Precise Concurrent Zero Knowledge. (EUROCRYPT 2008) O. Pandey, R. Pass, A. Sahai, W. Tseng and M. Venkitasubramaniam. Precise zero knowledge introduced by Micali and Pass (STOC 06) guarantees that the view of any verifier V can be simulated in time closely related to the actual (as opposed to worst-case) time spent by V in the generated view. We provide the first constructions of precise concurrent zero-knowledge protocols. Our constructions have essentially optimal precision; consequently this improves also upon the previously tightest non-precise concurrent zero-knowledge protocols by Kilian and Petrank (STOC 01) and Prabhakaran, Rosen and Sahai (FOCS 02) whose simulators have a quadratic worst-case overhead. Additionally, we achieve a statistically-precise concurrent zero-knowledge property—which requires simulation of unbounded verifiers participating in an unbounded number of concurrent executions; as such we obtain the first (even non-precise) concurrent zero-knowledge protocols which handle verifiers participating in a super-polynomial number of concurrent executions.	PDF
	On Constant-Round Concurrent Zero-Knowledge. (TCC 2008) R. Pass, M. Venkitasubramaniam. Loosely speaking, an interactive proof is said to be zero- knowledge if the view of every "efficient" verifier can be "efficiently" simulated. An outstanding open question regarding zero-knowledge is whether constant-round concurrent zero-knowledge proofs exists for non- trivial languages. We answer this question to the affirmative when mod- eling "efficient adversaries" as probabilistic quasi-polynomial time ma- chines (instead of the traditional notion of probabilistic polynomial-time machines).	PDF
	Concurrent Non-Malleable Commitments from One-way Functions (TCC 2008) H. Lin, R. Pass, M. Venkitasubramaniam. We show the existence of concurrent non-malleable commitments based on the existence of one-way functions. Our proof of security only requires the use of black-box techniques, and additionally provides an arguably simplified proof of the existence of even stand-alone secure non-malleable commitments.	PDF
	An Efficient Parallel Repetition Theorem for Arthur-Merlin Games. (STOC 2007) R. Pass, A. M. Venkitasubramaniam. We show a parallel-repetition theorem for constant-round Arthur-Merlin Games, using an efficient reduction. As a consequence, we show that parallel repetition reduces the soundness-error at an optimal rate (up to a negligible factor) in constant-round public-coin argument systems, and constant-round public-coin proofs of knowledge. The former of these results resolves an open question posed by Bellare, Impagliazzo and Naor (FOCS '97).	PDF
	l-Diversity: Privacy Beyond k-Anonymity. (TKDD 2007) A. Machanavajjhala, D. Kifer, J.Gehrke and M. Venkitasubramaniam. Publishing data about individuals without revealing sensitive information about them is an important problem. In recent years, a new definition of privacy called k-anonymity has gained popularity. In a k-anonymized dataset, each record is indistinguishable from at least k-1 other records with respect to certain "identifying" attributes. In this paper we show using two simple attacks that a k-anonymized dataset has some subtle, but severe privacy problems. First, an attacker can discover the values of sensitive attributes when there is little diversity in those sensitive attributes. This is a known problem. Second, attackers often have background knowledge, and we show that k-anonymity does not guarantee privacy against attackers using background knowledge. We give a detailed analysis of these two attacks and we propose a novel and powerful privacy criterion called l-diversity that can defend against such attacks. In addition to building a formal foundation for l-diversity, we show in an experimental evaluation that l-diversity is practical and can be implemented efficiently.	PDF
	l-Diversity: Privacy Beyond k-Anonymity. (ICDE 2006) A. Machanavajjhala, J.Gehrke, D. Kifer and M. Venkitasubramaniam. Winner of the IEEE ICDE Influential Paper 2017 Publishing data about individuals without revealing sensitive information about them is an important problem. In recent years, a new definition of privacy called k-anonymity has gained popularity. In a k-anonymized dataset, each record is indistinguishable from at least k-1 other records with respect to certain "identifying" attributes. In this paper we show with two simple attacks that a k-anonymized dataset has some subtle, but severe privacy problems. First, we show that an attacker can discover the values of sensitive attributes when there is little diversity in those sensitive attributes. Second, attackers often have background knowledge, and we show that k-anonymity does not guarantee privacy against attackers using background knowledge. We give a detailed analysis of these two attacks and we propose a novel and powerful privacy definition called l-diversity. In addition to building a formal foundation for l-diversity, we show in an experimental evaluation that l-diversity is practical and can be implemented efficiently.	PDF
	Trusted CVS. (STD3S - ICDE Workshops) M. Venkitasubramaniam, A. Machanavajjhala, D. Martin and J. Gehrke. The CVS (Concurrent Versions System) software is a popular method for recording modifications to data objects, in addition to concurrent access to data in a multi-user environment. In current implementations, all users have to trust that the CVS server performs all user operations as instructed. In this paper, we develop protocols that allow users to verify that the server has been compromised, and that it has performed exactly the users’ operations on the data. We first show that communication between users is necessary to guarantee that users can detect that the server has been compromised. We then propose efficient protocols that fast enable detection of server integrity under CVS workloads. Our techniques also have applications in the outsourcing model where multiple users own a common database maintained by an untrusted third-party vendor.	PDF
	On Byzantine Agreement over (2, 3)-Uniform Hypergraphs. (DISC 2004) D. V. S. Ravikant, M. Venkitasubramaniam, V. Srikanth, K. Srinathan and C. P. Rangan. Byzantine Agreement is possible on a network consists of only unicast channels (i.e. a 2-uniform hypergraph) if and only if n > 3t (Pease et. al. [PSL80]). However, Fitzi and Maurer ([FM00]) show that if, in addition to all unicast channels, there exists local broadcast among every three processes in the network (i.e. a complete (2,3)-uniform hypergraph), n>2t is necessary and sufficient for Byzantine agreement. In this paper, we show that optimum tolerance of n>2t can be achieved even if a substantial fraction of the local broadcast channels are not available. Specifically, we model the network as a (2,3)-uniform hypergraph H = (P,E), where P denotes the set of n processes and E is a set of 2-tuples and/or 3-tuples of processes (edges or 3-hyperedges), wherein each 3-hyperedge represents a local broadcast among the three processes; we obtain a characterization of the hypergraphs on which Byzantine agreement is possible. Using this characterization, we show that for n=2t+1, (2/3t3 + Theta(t2)) 3-hyperedges are necessary and sufficient to enable Byzantine agreement. This settles an open problem raised by Fitzi and Maurer in [FM00]. An efficient protocol is also given whenever Byzantine agreement is possible.	PDF
	Brief announcement: On the round complexity of distributed consensus over synchronous networks. (PODC 2004) D. V. S. Ravikant, M. Venkitasubramaniam, V. Srikanth, K. Srinathan and C. P. Rangan. In a synchronous network, it is well-known that t + 1 rounds are necessary and sufficient to achieve distributed consensus tolerating t stopping faults[2]. In this work, we show that in a network consisting of all k-cast channels, the corresponding number of rounds is floor[(t - 1)/k] + 2.	PDF

This material is based upon work supported by the National Science Foundation and Google. Any opinions, findings, and conclusions or recommendations expressed in these publications are those of the author(s) and do not necessarily reflect the views of the National Science Foundation and Google.